import java.util.*;

class Pos{
    int x;
    int y;
    public Pos(int x , int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString() {
        return "[" + this.x + "," + this.y + "]";
    }
}

public class Leetcode_10 {

    List<Pos> list = new ArrayList<>();
    int ans = Integer.MAX_VALUE;
    Map<Integer , List<Pos>> map = new HashMap<>();

    public void dfs(int x , int y , int ex , int ey , int[][] grid , int pos, int sum) {
        if(x == ex && y == ey) {
            list.add(pos , new Pos(x , y));
            List<Pos> a = new ArrayList<>();
            for(int i = 0 ; i < 5 ; i++){
                a.add(list.get(i));
            }
            map.put((sum + grid[ex][ey]) , a);
//            System.out.print(",路径和为:" + (sum + grid[ex][ey]));
            ans = Math.min(ans , (sum + grid[ex][ey]));
//            System.out.println();
        }

        for(int i = 0 ; i < 2 ; i++) {
            if(i == 0) {    //向右走
                if((x + 1) < grid[0].length) {
                    list.add(pos , new Pos(x , y));
                    dfs(x + 1 , y , ex , ey , grid , pos + 1 , sum + grid[x][y]);
                }
            } else {
                if((y + 1) < grid.length) {
                    list.add(pos , new Pos(x , y));
                    dfs(x , y + 1 , ex , ey , grid , pos + 1 , sum + grid[x][y]);
                }
            }
        }

    }

    public static void main(String[] args) {

        Leetcode_10 main = new Leetcode_10();

        int[][] grid = {
                {1,3,1},
                {1,4,1},
                {4,2,1}
        };

        main.dfs(0 , 0 , 2 , 2 , grid , 0 , 0);

        System.out.println("最短路径:" + main.map.get(main.ans));

    }
}
